package com.sicheng.lc.杂题.栈;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/20 12:52
 */
public class 弹栈序列 {
    /**
     * 输入两个整数序列，第一个序列表示栈的压入顺序，
     * 请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
     * <p>
     * 例如序列 1,2,3,4,5 是某栈的压入顺序，
     * 序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列，但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。
     */

    public boolean isRight(int[] nums1, int[] nums2) {
        if (nums1.length != nums2.length)
            return false;
        int top = -1;
        int i = 0, j = 0;
        for (; j < nums1.length && i < nums1.length; i++) {
            while (j < nums1.length && nums1[j] != nums2[i]) {
                if (top >= 0) {
                    nums1[++top] = nums1[j];
                }
                j++;
            }
            if (j < nums1.length && nums1[j] == nums2[i]) {
                if (top < 0)
                    top = j - 1;
                j++;
            }
        }

        while (i < nums1.length) {
            if (nums1[top] != nums2[i])
                return false;
            i++;
            top--;
        }
        return true;
    }

    public static void main(String[] args) {
        弹栈序列 s = new 弹栈序列();
        int[] nums1 = {1, 2, 3, 4, 5};
        int[] nums2 = {4, 5, 3, 2, 1};
        System.out.println(s.isRight(nums1, nums2));
    }
}
